//给你一个链表数组，每个链表都已经按升序排列。 
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。 
//
// 
//
// 示例 1： 
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
// 
//
// 示例 2： 
//
// 输入：lists = []
//输出：[]
// 
//
// 示例 3： 
//
// 输入：lists = [[]]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] 按 升序 排列 
// lists[i].length 的总和不超过 10^4 
// 
//
// Related Topics 链表 分治 堆（优先队列） 归并排序 👍 2586 👎 0


package LeetCode.editor.cn;

import java.util.PriorityQueue;

/**
 * @author ldltd
 * @date 2023-08-13 02:43:50
 * @description 23.合并 K 个升序链表
 */
public class MergeKSortedLists{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new MergeKSortedLists().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 //Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
		 /*朴素算法，两个两个的合并，时间复杂度O(k^2*n)*/
	public ListNode mergeKLists2(ListNode[] lists) {
		ListNode ans = null;
		for (int i = 0; i < lists.length; ++i) {
			ans = mergeTwoLists(ans, lists[i]);
		}
		return ans;
	}
		/*分治  时间Ollogm  空间ologm 其中l是所有节点总长度，m是lists长度
		* 把k个链表配对，k个链表被分为k/2个，每个2n/k,然后是k/4，k/8*/
	public ListNode mergeKLists1(ListNode[] lists) {
		return merge(lists, 0, lists.length - 1);
	}

	public ListNode merge(ListNode[] lists, int l, int r) {
		if (l == r) {
			return lists[l];
		}
		if (l > r) {
			return null;
		}
		int mid = (l + r) >> 1;
		return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
	}

	public ListNode mergeTwoLists(ListNode a, ListNode b) {
		if (a == null || b == null) {
			return a != null ? a : b;
		}
		ListNode head = new ListNode(0);
		ListNode tail = head, aPtr = a, bPtr = b;
		while (aPtr != null && bPtr != null) {
			if (aPtr.val < bPtr.val) {
				tail.next = aPtr;
				aPtr = aPtr.next;
			} else {
				tail.next = bPtr;
				bPtr = bPtr.next;
			}
			tail = tail.next;
		}
		tail.next = (aPtr != null ? aPtr : bPtr);
		return head.next;
	}
	//自底向上，迭代，比如把0,1合并放在0，2,3合并放在2 以此类推 0 2到0，4 6到 4
	public ListNode mergeKLists(ListNode[] lists) {
		int m = lists.length;
		if (m == 0) {
			return null;
		}
		//迭代先从间隔1开始
		for (int step = 1; step < m; step *= 2) {
			//每次需要合并2个，跳过间隔数比如0，4  下一对就0+4*2 0+4*2+4 8 和12
			for (int i = 0; i < m - step; i += step * 2) {
				lists[i] = mergeTwoLists(lists[i], lists[i + step]);
			}
		}
		return lists[0];
	}

	/*使用优先队列*/
	public ListNode mergeKLists3(ListNode[] lists) {
		if(lists==null||lists.length==0) return null;
		PriorityQueue<ListNode> q=new PriorityQueue<>(lists.length,(o1,o2)->o1.val-o2.val);

		//其他写法
		// var pq = Stream.of(lists).filter(node -> node != null).collect(Collectors.toCollection(() -> new PriorityQueue<ListNode>((a,b) -> a.val - b.val)));
		ListNode res = new ListNode(0);
		ListNode p=res;
		for (ListNode node : lists) {
			if(node!=null) q.add(node);
		}
		while(!q.isEmpty()){
			p.next=q.poll();
			p=p.next;
			if(p.next!=null) q.add(p.next);
		}
		return res.next;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
